package leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * @创建人 MBY381
 * @创建时间 2022/4/22 20:07
 * @描述 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 */
public class Solution42 {



    public int trap3(int[] height) {
        int ans=0;
        int left=0,right=height.length-1;
        int lmax=0,rmax=0;
        while(left<right){
            lmax=Math.max(height[left],lmax);
            rmax=Math.max(height[right],rmax);
            if(height[left]<height[right]){
                ans+=lmax-height[left];
                left++;
            }else{
                ans+=rmax-height[right];
                right--;
            }
        }
        return ans;
    }
    /**
     * 很好理解的双指针法
     *
     * @param height ？
     * @return 》
     */
    public int trap1(int[] height) {
        int ans = 0;
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        while (left < right) {
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);
            if (height[left] < height[right]) {
                ans += leftMax - height[left];
                ++left;
            } else {
                ans += rightMax - height[right];
                --right;
            }
        }
        return ans;
    }
    class Bucket{
        private int start;
        private int end;
        public void setStart(int start) {
            this.start = start;
        }
        public void setEnd(int end) {
            this.end = end;
        }
    }
    public int trap(int[] height) {
        List<Bucket> li=new ArrayList<>();
        int start=0,end=0,index=0;
        while(end+1< height.length){
            Bucket bucket=new Bucket();
            boolean isValid=true;
            start=end+1;
            index=start;
            while(index< height.length){
                if(height[index]>= height[start]){
                    isValid=false;
                    end++;
                    break;
                }
                index++;
            }
            if(isValid){
                bucket.setStart(start);
                bucket.setEnd(end);
                li.add(bucket);
            }
        }
        return 1;
    }
}
